1. Field of the Invention
The present invention relates to a functional language oriented processor like a lisp (namely a list Processor) which processes symbols or codes in place of numerals, particularly to a functional language oriented processor having such a structure that the environment in which functions are executed (what is used as a value of a variable) is stored as a stack structure in the memory within the computer system.
2. Description of the Prior Art
A Lisp deals, as shown in FIG. 1, with a binary tree list, namely a relationship of codes representing a tree structure (FIG. 1(A)) which is a gathering of nodes and branches and not including a closed loop or circular list. Namely, it stores the relationships of codes or symbols indicated by the tree structure as shown in FIG. 1(A) in the main memory in the form shown in FIG. 1(C) after such relationships are converted to the binary tree structure where each node has two branches. In other words, where each list cell or node is composed of one or two words of main memory and where each cell is composed of two (right and left) portions or fields. That is, the left portion of each cell usually stores the bit pattern of a code or symbol, for example, the code of letter A, while the right portion stores a pointer address or link to the next code or symbol connected to the code of the present node, thus indicating the connection of two cells. Therefore, the relationship of list cells in FIG. 1(C) realizes the binary tree list of FIG. 1(B) in the memory circuit. The Lisp is capable of obtaining the desired list structure by dynamically converting such list structure by executing a List language using the processor.
In the Lisp, programming means having a function which is formed by combining the following five basic functions which are necessary for converting the binary tree list is provided and a value for such function is obtained by executing the program.
The five basic functions are as follow:
(a) car [X]
Having a value of the binary tree list located at the end of the left branch of the binary tree list X;
(b) cdr [X]
Having a value of the binary tree list located at the end of the right branch of the binary tree list X;
(c) cons [X:Y]
Having a value of a new binary tree list formed by providing a new list cell where the left branch is considered the binary tree list X while the right branch the binary tree list Y;
(d) atom [X]
When X is an atom, it is considered as True (indicated by "T" or "*T*") and otherwise, it is considered as False (indicated by atom of "NIL"); and
(e) eq [X:Y]
When X and Y are the same binary tree list, it is considered as true ("T" or "*T*") and otherwise it is considered as False (indicated by "NIL").
For example, when f(x, y)=x.sup.y +y.sup.x, a value of f(2, 3) becomes as follows, .lambda.[[X, Y]; X.sup.Y +Y.sup.X ][2, 3]=2.sup.3 +3.sup.2 by f=.lambda.[[X, Y]; X.sup.Y +Y.sup.X ], and the corresponding relationship between variables can be defined clearly.
Here, (X, Y) is a variable called the formal argument and (2, 3) is a value of (X, Y) at this time called the actual argument. Substitution of the actual argument (2, 3) into the formal argument (X, Y) is called binding and obtaining the value of functions by binding the actual argement to the formal argument, in this case, formation of the wanted list of 2.sup.3 +3.sup.2 requires the execution of the Lisp. Therefore, there is a problem in the Lisp, namely in the functional language oriented processor concerning how to bind the formal argument to the actual argument.
In the processor which is an object of the present invention, a bind value of a variable is stored in a pair of comprising a variable name and a value for the linear list (environment list) on a FILO (First In Last Out or Push down Pop up) type stack. Here, the FILO type stack stores the data in a memory circuit in a binary tree list structure by using an indirect address system (namely, an address of a cell connected next to a certain cell is stored). The sequence where the pair of a variable name and a value is the same as that where the function using a variable of the argument is used. Such a method of forming this environment is generally called dynamic scoping. When searching for a value of a variable, the environment lists (or stacks) are sequentially retrieved, as a basic operation, from the heading of the list, namely from the newer list and the lists found are accessed sequentially beginning from the list found first. This method is called a Deep Bind type variable binding.
In general, the program structure and execution mode of the functional language are as follows and as shown in FIG. 2. For example, the actual argument (2, 3) is combined, that is, bound to the formal argument (X, Y) of the function to be called, namely the function, f=.lambda.[[X, Y]; X.sup.Y +Y.sup.X ], the called (started) function executes the specified procedures by referencing the actual argument or a global variable transferred thereto, that is, substituted therefor and a value of such function (2.sup.3 +3.sup.2) is returned to the calling side. However, a side effect (that is, a changing of the environment) is not caused. Explanation of the side effect is omitted here because it is not directly related to the subject matter of the present invention.
When calling a function, methods of binding the actual argument to the formal argument are classified into the deep bind method and a shallow bind method.
As explained above, the deep bind method is a structure of an environment where a pair of the variable name (X, Y) and a value (2, 3) is stored in the form of a stack structure as the linear list, variables are sequentially referenced from a variable which has been previously bound and a value of a variable found first is used.
Namely, in the deep bind method, as shown in FIG. 3(A), a word, which is the storing unit of main memory, is divided into the right and left portions or fields forming a cell. The left portion stores variable names, while the right portion stores the address of the next cell to be connected and thereby indicates a variable of the next cell. In case there are many variables, these are connected as shown in FIG. 3(a) and the FILO type stack can be structured equivalently as shown in FIG. 3(B).
When binding a value to the formal argument while calling a function, a pair of the name and value is related from the direction from which the retrieval of the environment list (or environment stack) is started and the retrieval start point is updated as the header of newly added items. Namely, in the main memory of FIG. 3, the starting point corresponds to that the one cell n+1 provided in the heading area and the header cell is connected to the next cell n. In FIG. 3(B), the starting point corresponds to the push operation A for the stack and the cell having the variable name n+1 and a value (n+1) is entered in the latest stage of the stack by the push operation. At the time of returning a function, the retrieval start pointer is returned to the condition where the function was called. That is, in the main memory circuit of FIG. 3(A), it corresponds to where the cell n is placed in the heading area by extracting the heading cell n+1 and in FIG. 3(B) it means that n+1 and its value (n+1) are taken out of the stack by the pop operation B. The deep bind method has the following advantage in that the push-pop operation of a stack is simplified and overhead for bind processing for the argument of the variable at the time of calling a function or overhead for unbind processing for the argument of the variable at the time of returning from a function are comparatively little. Meanwhile it has a following disadvantage in that a longer time is required for referring to the variables not bound, namely the variables placed in the deep area of stack, like a global variables (also called free variable) must be found which requires considerable time.
In the case of the shallow bind method, a random access area (called the value cell) is provided for each variable in order to hold a value of the variable, the actual argument is stored into the value cell of argument of the variable at the time of calling the functions, values which are precedingly stored in the value cell are stored as a pair of a name and old value in the linear list (or stack), variables can be referred to only by reading the corresponding value cell, an an old value which has been stored in the linear list (or stack) is returned to the value cell of argument variable at the time of returning from the function call. The shallow bind method has an advantage in that variable (global) reference time is comparatively short, while it has a disadvantage in that overhead for bind processing for argument variable at the time of calling functions and overhead for the unbind processing at the time of returning the function are comparatively large.
As explained above, the deep bind method excels in a rate of bind/unbind processing of argument as compared with the shallow bind method but requires a longer time for refrence to an unbound variable particularly to a global variable. Namely, variables are referred to by the sequential method where the pointer is changed one by one, thus requiring a longer processing time.